二分图博弈

博弈论趣题

问题

有一个二分图,点带点权,分成A集合和B集合。两人轮流选点,每次只能选和上一次有连边的点(第一次从A集合任选),选到一个点把点权1-1,点权为00的点不能再选。最后不能选者失败。求一个先手必胜策略或说明先手必败。

结论

先手应该选择一个不一定在最大匹配中的点。即存在一个最大匹配使得该点没有被匹配满。如果这样的点不存在则先手必败。

证明

对于任意一个最大匹配,首先选择一个不在该匹配中的点,对于对手选的每个点,我们都选择在匹配中和它对应的那个点。可以证明对手在任何时候都不能选择不在匹配中的点(否则把所有选过的点连起来是一条增广路,该匹配不是最大匹配),先手必胜。否则,如果先手选择了一个必定在最大匹配中的点,该点点权1-1后最大匹配必然跟着1-1,那么原来的最大匹配去掉了该点和B集合对应的点这组匹配后仍然是最大匹配。此时该对应点就是成为了不一定在最大匹配中的点,按照上面的证明后手必胜。(也可以用归纳法证明)

如何求这样的点

使用网络流求出最大匹配,然后在残余网络上dfs。记超级原点为SS,超级汇点为TT,则在SS一侧的点中,SS可达的就是不一定在最大匹配中的点。逆命题也成立。TT一侧同理。

这个方法的证明

对于SS一侧SS可达的点xx,若原图SxS→x边没有流满显然成立,否则沿着SS到x的路径xSS→\text{S到x的路径}→x→S这条回路加流量,变化后的最大流中SxS→x边就没有流满。

例题(然而并没有地方提交)

小A和小B正在进行一场博弈,规则如下:开始时,有若干个正整数。游戏的第一步中小A先任选一个数删去,之后两个人轮流操作,每次选择一个数并删去。设当前选择的数为xx,前一个选择的数为yy,则xy\frac{x}{y}yx\frac{y}{x}中必须有一个质数。无法操作者负。对于给定的初始数集,你需要确定:小A是否有必胜策略?如果有,小A在第一步中可以选择哪些数?

输入第一行为一个正整数nn;接下来nn行,每行两个正整数p,qp,q,表示正整数pp在一开始的数中出现了qq次。

若小A没有必胜策略,输出-1;否则,升序输出小A第一步可以选择,以确保自己必胜的数。